from typing import List


class Solution:
    """
    剑指 Offer 04. 二维数组中的查找
    """
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        m, n = len(matrix), len(matrix[0])
        i, j = 0, len(matrix[0]) - 1
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1
        return False


if __name__ == '__main__':
    s = Solution()
    mat = [
        [1, 4, 7, 11, 15],
        [2, 5, 8, 12, 19],
        [3, 6, 9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30]
    ]
    print(s.findNumberIn2DArray(mat, 5))
    print(s.findNumberIn2DArray(mat, 16))
